package com.gorkr.labuladong.data_struct.array.windows;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/06/07 00:51
 **/
public class M438FindAllAnagramsInAString {

    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> res = new ArrayList<>();

        HashMap<Character, Integer> need = new HashMap<>();
        for (Character c :
                p.toCharArray()
        ) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        HashMap<Character, Integer> window = new HashMap<>();

        int left=0, right = 0;
        int start = 0, len = Integer.MAX_VALUE;
        int valid = 0;

        while (right<s.length()){
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }


            while (valid==need.size()){

                if((right-left)==p.length()){
//                    if(!s.substring(left,right).equals(p)){
                        res.add(left);
//                    }

                }

                char b = s.charAt(left);
                left++;
                if(need.containsKey(b)){
                    window.put(b,window.get(b)-1);
                    if(window.get(b)<need.get(b)){
                        valid--;
                    }
                }

            }

        }



        return res;
    }

    @Test
    public void test(){
        String s = "cbaebabacd", p = "abc";
//        String s = "abab", p = "ab";
        System.out.println(findAnagrams(s, p).toString());
    }


}
    